# 零钱兑换

# 零钱
coins = [3, 5, 11]
# 凑得金额
amount = 16

def find_min(coins, amount):
    """ 动态规划: 递归解决 """
    if amount == 11:
        return 1
    elif amount == 5:
        return 1
    elif amount == 1:
        return 1
    else: 
        if amount > 11:   
            return min(find_min(coins, amount - 1), find_min(coins, amount-5), find_min(coins, amount-11)) + 1
        elif amount > 5:
            return min(find_min(coins, amount - 1), find_min(coins, amount-5)) + 1
        else: 
            return amount


def find_min_plus(coins, amount):
    """ 动态规划 """
    min_c = [float('inf')] * (amount + 1)
    min_c[0] = 0
    mini = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            mini = min(min_c[i-coin] + 1, min_c[i]) 
            min_c[i] = mini

    print(min_c)
    if min_c[amount] == float('inf'):
        return -1
    else:
        return min_c[amount]


min_a = find_min(coins, amount)
print(min_a)

